package com.linyaonan.leetcode.easy._993;

/**
 * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
 *
 * 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
 *
 * 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
 *
 * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
 */
class Solution {

    class KK {
        public int deep;
        public int parentVal;

        public KK(int _deep, int _parentVal) {
            this.deep = _deep;
            this.parentVal = _parentVal;
        }

    }

    public boolean isCousins(TreeNode root, int x, int y) {
        KK k1 = getDeepAndParent(root, x);
        KK k2 = getDeepAndParent(root, y);

        return k1 != null && k2 != null && k1.deep == k2.deep && k1.parentVal != k2.parentVal;
    }

    /**
     * 从一棵树上找到对应深度以及父节点，按照逗号分割
     * @param root
     * @param t
     * @return
     */
    public KK getDeepAndParent(TreeNode root, int t) {
        if (root.val == t) {
            return new KK(0, 0);
        }
        return dfs(root, t, 1, null);
    }

    private KK dfs(TreeNode root, int t, int deep, TreeNode par) {
        if (root == null) {
            return null;
        }
        if (root.val == t) {
            return new KK(deep,par.val);
        } else {
            KK l1 = dfs(root.left, t, deep + 1, root);
            if (l1 != null) {
                return l1;
            }
            KK l2 = dfs(root.right, t, deep + 1, root);
            return l2;
        }
    }
}